package link

import (
	"algorithm/myStruct"
	"container/list"
	"errors"
	"sync"
)

// --------------------------listQueue---------------------------------
type ListQueue struct {
	l *myStruct.List
}

func NewListQueue() *ListQueue {
	return &ListQueue{l: myStruct.NewList()}
}

func (lq *ListQueue) Push(e interface{}) {
	lq.l.PushFront(e)
}

func (lq *ListQueue) Pop() interface{} {
	e := lq.l.PopBack()
	if e != nil {
		return e.Val
	}

	return nil
}

// --------------------------listQueue---------------------------------

// --------------------------arrayQueue---------------------------------
type ArrayQueue struct {
	a         []interface{}
	pushIndex int
	popIndex  int
	size      int
	limit     int
}

func NewArrayQueue(limit int) *ArrayQueue {
	return &ArrayQueue{
		a:         make([]interface{}, limit),
		pushIndex: 0,
		popIndex:  0,
		size:      0,
		limit:     limit,
	}
}

func (aq *ArrayQueue) Push(e interface{}) error {
	if aq.size == aq.limit {
		return errors.New("queue full")
	}

	aq.a[aq.pushIndex] = e
	aq.pushIndex = aq.nextIndex(aq.pushIndex)
	aq.size++

	return nil
}

func (aq *ArrayQueue) Pop() interface{} {
	if aq.size == 0 {
		return nil
	}

	e := aq.a[aq.popIndex]
	aq.size--
	aq.popIndex = aq.nextIndex(aq.popIndex)

	return e
}

func (aq *ArrayQueue) nextIndex(i int) int {
	if i+1 == aq.limit {
		return 0
	}

	return i + 1
}

// --------------------------arrayQueue---------------------------------

// --------------------------queueStack---------------------------------
// 用栈实现队列 https://leetcode-cn.com/problems/implement-queue-using-stacks/
type MyQueue struct {
	pushStack *list.List
	popStack  *list.List
}

func Constructor2() MyQueue {
	return MyQueue{
		pushStack: list.New(),
		popStack:  list.New(),
	}
}

func (this *MyQueue) Push(x int) {
	this.pushStack.PushBack(x)
}

func (this *MyQueue) Pop() int {
	if this.Empty() {
		return 0
	}

	if this.popStack.Len() == 0 {
		var popLock sync.Mutex
		popLock.Lock()
		defer popLock.Unlock()
		for this.pushStack.Len() > 0 {
			this.popStack.PushBack(this.pushStack.Remove(this.pushStack.Back()))
		}
	}

	return this.popStack.Remove(this.popStack.Back()).(int)
}

func (this *MyQueue) Peek() int {
	if this.Empty() {
		return 0
	}

	if this.popStack.Len() == 0 {
		var popLock sync.Mutex
		popLock.Lock()
		defer popLock.Unlock()
		for this.pushStack.Len() > 0 {
			this.popStack.PushBack(this.pushStack.Remove(this.pushStack.Back()))
		}
	}

	return this.popStack.Back().Value.(int)
}

func (this *MyQueue) Empty() bool {
	return this.popStack.Len() == 0 && this.pushStack.Len() == 0
}

// --------------------------queueStack---------------------------------

// --------------------------递归求最大值---------------------------------
func GetMax(data []int) int {
	if len(data) < 1 {
		return 0
	}

	return process(data, 0, len(data)-1)
}
func process(data []int, s, e int) int {
	if s == e {
		return data[s]
	}

	m := s + ((e - s) >> 1)

	return max(process(data, s, m), process(data, m+1, e))
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

// --------------------------递归求最大值---------------------------------
